package com.hyb.algorithm.data.struct.backtrack;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;

/**
 * 93. 复原 IP 地址
 * https://leetcode.cn/problems/restore-ip-addresses/
 *
 * @author: ybhu
 * @create: 2023/12/27 11:46
 */
public class RestoreIpAddresses2 {


    public static void main(String[] args) {
        //List<String> res=   new RestoreIpAddresses2().restoreIpAddresses("25525511135");

        List<String> res=   new RestoreIpAddresses2().restoreIpAddresses("101023");

        //List<String> res=   new RestoreIpAddresses2().restoreIpAddresses("0000");

        System.out.println(JSONObject.toJSON(res));
    }


    //IP有 四个 segment  xx.xx.xx.xx
    private int[] segment = new int[4];
    private int segmentCount = 4;

    private List<String> res;

    public List<String> restoreIpAddresses(String s) {

        res = new ArrayList<String>();
        dfs(s, 0, 0);

        return res;

    }

    public void dfs(String s, int segmentStart, int segmentIndex) {
        //到第4个端
        if (segmentIndex == segmentCount) {
            //说明拼接成功处理
            if (segmentStart == s.length() ) {
                printToResult();
            }
            return;
        }





        // 4端还没满，但是到了字符串长度限制了
        if (segmentStart == s.length() ) {
            return;
        }





        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        //有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

        if (s.charAt(segmentStart) == '0') {
            segment[segmentIndex] = 0;
            dfs(s, segmentStart + 1, segmentIndex + 1);
            return;
        }



        // 一般情况，枚举每一种可能性并递归  255 255 11135
        int val = 0;
        for (int i = segmentStart; i < s.length(); i++) {
            val = val * 10 + (s.charAt(i) - '0');

            System.out.println(String.format("segmentIndex={%s}, addr={%s},i={%s}",segmentIndex,val,i));
            if (val > 0 && val <= 255) {
                segment[segmentIndex] = val;
                //这里要注意 不是用  segmentStart 用 i
                dfs(s, i + 1, segmentIndex + 1);
            }else
            {
                //System.out.println(String.format("segmentIndex={%s}, addr={%s},i={%s}",segmentIndex,val,i));
                break;
            }


        }

    }


    public void printToResult() {

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < segment.length; i++) {
            stringBuilder.append(segment[i]);

            if (i != segment.length - 1) {
                stringBuilder.append(".");
            }
        }
        res.add(stringBuilder.toString());
    }



}
